package offerbook;

/**
 * 任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）
 * 如：1~13中包含1的数字有1、10、11、12、13因此共出现6次
 * <p>
 * 方式1：对任意一个数进行除10取余，判断最后一位是否是1，累加。
 * 时间复杂度O(n logn)
 * 方式2：利用数自身的规律，给定1-n，通过计算n的位数以及n的最高位，
 * https://blog.csdn.net/yi_Afly/article/details/52012593?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
 */
public class Code32_NumberOf1Between1AndN {

    /**
     * 方式1：对任意一个数进行除10取余，判断最后一位是否是1，累加。
     * <p>
     * 时间复杂度O(n logn), 输入一个n，它的位数是log(10,n)+1 ===也就是logn级别
     */
    public static int getNumOf1Between1AndN(int n) {
        //非法，约定是0
        if (n <= 0) {
            return 0;
        }
        int num = 0;
        for (int i = 1; i <= n; i++) {
            int res = i;
            while (res != 0) {
                if (res % 10 == 1) {
                    num++;
                }
                res = res / 10;
            }
        }
        return num;
    }

    public int getNumOf1Between1AndN_2(int n) {
        if (n < 1)  return 0;
        int count = 0;
        //权重从个位考虑
        int base = 1;
        int round = n;
        while (round > 0) {
            //如534,个位权重是4
            int weight = round % 10;
            //考虑下一次十位
            round /= 10;
            //基本条件是 round * base ,这里是53*1
            count += round * base;
            //考虑当前权重位是否为1，若为1，则看base低一级下的个数，为k，则是 K+1
            //比如假设base = 10,round = 5,  514, 十位基本条件是5*10
            //又因为十位为1，所以还要 + 4+1
            if (weight == 1)
                count += (n % base) + 1;
            //如果当前权重比1大，则加上一个完整的轮数
            else if (weight > 1)
                count += base;
            //权重*10
            base *= 10;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(getNumOf1Between1AndN(21305));
    }
}
